home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 3: Developer Tools / Linux Cubed Series 3 - Developer Tools.iso / devel / lang / lisp / stk-3.002 / stk-3 / STk-3.1 / Src / vector.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-05-17  |  4.9 KB  |  217 lines

  1. /*
  2.  *
  3.  * v e c t o r . c             -- vectors management
  4.  *
  5.  * Copyright ⌐ 1993-1996 Erick Gallesio - I3S-CNRS/ESSI <eg@unice.fr>
  6.  * 
  7.  *
  8.  * Permission to use, copy, and/or distribute this software and its
  9.  * documentation for any purpose and without fee is hereby granted, provided
  10.  * that both the above copyright notice and this permission notice appear in
  11.  * all copies and derived works.  Fees for distribution or use of this
  12.  * software or derived works may only be charged with express written
  13.  * permission of the copyright holder.  
  14.  * This software is provided ``as is'' without express or implied warranty.
  15.  *
  16.  * This software is a derivative work of other copyrighted softwares; the
  17.  * copyright notices of these softwares are placed in the file COPYRIGHTS
  18.  *
  19.  *           Author: Erick Gallesio [eg@unice.fr]
  20.  *    Creation date: ???
  21.  * Last file update: 10-Feb-1996 12:46
  22.  */
  23.  
  24. #include <string.h>
  25. #include "stk.h"
  26.  
  27.  
  28. SCM STk_makevect(int len, SCM init)
  29. {
  30.   long j;
  31.   SCM  z;
  32.  
  33.   STk_disallow_sigint();
  34.   NEWCELL(z, tc_vector);
  35.  
  36.   z->storage_as.vector.dim  = len;
  37.   z->storage_as.vector.data = (SCM *) must_malloc(len * sizeof(SCM));
  38.  
  39.   if (init)
  40.     for(j=0 ;j<len; j++) z->storage_as.vector.data[j] = init;
  41.  
  42.   STk_allow_sigint();
  43.   return z;
  44. }
  45.  
  46.  
  47. /**** Section 6.8  ****/
  48.  
  49. PRIMITIVE STk_vectorp(SCM obj)
  50. {
  51.   return VECTORP(obj) ? Truth: Ntruth;
  52. }
  53.  
  54. PRIMITIVE STk_make_vector(SCM len, SCM init)
  55. {
  56.   long k;
  57.  
  58.   if ((k=STk_integer_value(len))<0) Err("make-vector: bad vector length", len);
  59.   return STk_makevect(k, init);
  60. }
  61.  
  62. PRIMITIVE STk_vector(SCM l, int len)
  63. {
  64.   int j;
  65.   SCM z = STk_makevect(len, NULL);
  66.   
  67.   for (j = 0; j < len; j++, l=CDR(l)) {
  68.     VECT(z)[j] = CAR(l);
  69.   }
  70.   return z;
  71. }
  72.  
  73. PRIMITIVE STk_vector_length(SCM v)
  74. {
  75.   if NTYPEP(v, tc_vector) Err("vector-length: not a vector", v);
  76.   return STk_makeinteger((long) v->storage_as.vector.dim);
  77. }
  78.  
  79. PRIMITIVE STk_vector_ref(SCM v, SCM index)
  80. {
  81.   long k;
  82.  
  83.   if (NVECTORP(v))                  Err("vector-ref: not a vector", v);
  84.   if ((k=STk_integer_value(index)) < 0) Err("vector-ref: bad index", index);
  85.   if (k >= v->storage_as.vector.dim) 
  86.     Err("vector-ref: index out of bounds", index);
  87.   return VECT(v)[k];
  88. }
  89.  
  90. PRIMITIVE STk_vector_set(SCM v, SCM index, SCM value)
  91. {
  92.   long k;
  93.   
  94.   if (NVECTORP(v))             Err("vector-set!: not a vector", v);
  95.   if ((k=STk_integer_value(index)) < 0) Err("vector-set!: bad index", index);
  96.   if (k >= v->storage_as.vector.dim) 
  97.     Err("vector-set!: index out of bounds", index);
  98.   
  99.   VECT(v)[k] = value;
  100.   return UNDEFINED;
  101. }
  102.  
  103. PRIMITIVE STk_vector2list(SCM v)
  104. {
  105.   int j, len;
  106.   SCM z, tmp;
  107.  
  108.   if (NVECTORP(v)) Err("vector->list: not a vector", v);
  109.     
  110.   len = v->storage_as.vector.dim;
  111.   z   = NIL;
  112.  
  113.   for (j=0; j<len; j++) {
  114.     if (j == 0)
  115.       tmp = z = Cons(VECT(v)[j], NIL);
  116.     else 
  117.       tmp = CDR(tmp) = Cons(VECT(v)[j], NIL);
  118.   }
  119.   return z;
  120. }
  121.  
  122. PRIMITIVE STk_list2vector(SCM l)
  123. {
  124.   if (NCONSP(l) && NNULLP(l)) Err("list->vector: not a list", l);
  125.   return STk_vector(l, STk_llength(l));
  126. }
  127.  
  128.  
  129. PRIMITIVE STk_vector_fill(SCM v, SCM fill)
  130. {
  131.   int j, len;
  132.  
  133.   if (NVECTORP(v)) Err("vector-fill!: not a vector", v);
  134.   
  135.   for (j=0, len= v->storage_as.vector.dim; j < len; j++) 
  136.     VECT(v)[j] = fill;
  137.  
  138.   return UNDEFINED;
  139. }
  140.  
  141. /*
  142.  * 
  143.  * STk bonus
  144.  *
  145.  */
  146.  
  147. PRIMITIVE STk_vector_copy(SCM vect)
  148. {
  149.   SCM z;
  150.   int n;
  151.  
  152.   if (NVECTORP(vect)) Err("vector-copy: bad vector", vect);
  153.   n = vect->storage_as.vector.dim;
  154.   z = STk_makevect(n, NULL);
  155.   memcpy(VECT(z), VECT(vect), n * sizeof(struct obj*));
  156.   return z;
  157. }
  158.  
  159. PRIMITIVE STk_vector_resize(SCM vect, SCM size)
  160. {
  161.   long old_size, new_size;
  162.  
  163.   if (NVECTORP(vect))                  Err("vector-resize: bad vector", vect);
  164.   if ((new_size=STk_integer_value(size))<0) Err("vector-resize: bad new size",size);
  165.   
  166.   old_size                = vect->storage_as.vector.dim;
  167.   vect->storage_as.vector.dim  = new_size;
  168.   vect->storage_as.vector.data = must_realloc(vect->storage_as.vector.data, 
  169.                           new_size*sizeof(SCM));
  170.  
  171.   if (old_size < new_size) { /* Fill in new cells with an unbound value */
  172.     long i;
  173.     
  174.     for (i = old_size; i < new_size; i++) 
  175.       VECT(vect)[i] = UNBOUND;
  176.   }
  177.   return vect;
  178. }
  179.  
  180.  
  181. PRIMITIVE STk_sort(SCM obj, SCM test)
  182. {
  183.   SCM *v;
  184.   int list = 0;
  185.   register int i, j, incr, n;
  186.  
  187.   if (CONSP(obj) || NULLP(obj)) { list = 1; obj = STk_list2vector(obj); }
  188.   if (NVECTORP(obj)) Err("sort: bad object to sort", obj);
  189.   
  190.   obj = STk_vector_copy(obj);
  191.  
  192.   /* 
  193.    * Use a shell sort. It has good performance on small arrays
  194.    * This sort should have better performances than a cleverer one 
  195.    * for the sorts we'll have to do in STklos (which are always small
  196.    * arrays).
  197.    */
  198.  
  199.   v    = VECT(obj);
  200.   n    = obj->storage_as.vector.dim;
  201.  
  202.   for (incr = n / 2; incr; incr /= 2) {
  203.     for (i = incr; i < n; i++) {
  204.       for (j = i-incr; j >= 0; j -= incr) {
  205.     if (Apply(test, LIST2(v[j], v[j+incr])) != Ntruth) 
  206.       break;
  207.     else {
  208.       SCM tmp   = v[j+incr];
  209.       v[j+incr] = v[j];
  210.       v[j]        = tmp;
  211.     }
  212.       }
  213.     }
  214.   }
  215.   return list ? STk_vector2list(obj) : obj;
  216. }
  217.